package com.example.demo.Class25_singleStack;

import java.util.Stack;

/**
 * @program: java_base
 * @description: 可存入重复值的单调栈
 * @author: zhouhongtao
 * @happyCreateTime: 2022/03/05 15:21
 * 详见 package-info.java
 */
public class Code01_MonotonousStackDemo {


    // arr = [ 3, 1, 2, 3]
    //         0  1  2  3
    //  [
    //     0 : [-1,  1] 含义：原数组0 index位置 -1位置左边比他小 1index右边比他小
    //     1 : [-1, -1]
    //     2 : [ 1, -1]
    //     3 : [ 2, -1]
    //  ]

    /**
     * 自己写的错误代码，错的一塌糊涂
     *
     * @param arr
     * @return
     */
    public static int[][] getNearLessNoRepeat_wrongCode(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] ans = new int[arr.length - 1][2];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < arr.length; i++) {
            int[] row = new int[2];
            // 如果当前的数落不上去的时候，需要弹出，排好需
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer pop = stack.pop();
                row[1] = pop;
                row[0] = stack.isEmpty() ? -1 : stack.peek();
                ans[pop] = row;
            }
            stack.add(i);
        }
        while (!stack.isEmpty()) {
            int[] row = new int[2];
            row[1] = -1;

            Integer pop = stack.pop();
            row[0] = pop == null ? -1 : pop;
            if (pop != null) {
                ans[pop] = row;
            }
        }
        return ans;
    }


    public static int[][] getNearLess_my(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] ans = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer pop = stack.pop();
                //(leftLess)
                int left = stack.isEmpty() ? -1 : stack.peek();
                ans[pop][0] =
                //rightLess
                ans[pop][1] = i;
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            // left
            ans[pop][0] = stack.isEmpty() ? -1 : stack.peek();
            // right
            ans[pop][1] = -1;
        }
        return ans;
    }

    public static int[][] getNearLessNoRepeat_wrightCode(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] ans = new int[arr.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            // 如果当前的数落不上去的时候，需要弹出，排好需
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer pop = stack.pop();
                ans[pop][1] = i;
                ans[pop][0] = stack.isEmpty() ? -1 : stack.peek();
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            ans[pop][1] = -1;
            ans[pop][0] = stack.isEmpty() ? -1 : stack.peek();
        }
        return ans;
    }

    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        // 只存位置！
        Stack<Integer> stack = new Stack<>();
        // 当遍历到i位置的数，arr[i]
        for (int i = 0; i < arr.length; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                Integer j = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[i][0] = leftLessIndex;
                res[i][1] = j;
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            Integer j = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[j][0] = leftLessIndex;
            res[j][1] = -1;
        }
        return res;
    }


}
